629C - Famil Door and Brackets - CodeForces Solution

/*
设 f[i][j] 表示前 i 个，cnt[(]-cnt[)] 的数量为 j 的方案数。
这个可以做出 P,Q 的样子啊。
接下来枚举 P 的长度，lp+lq+ls=n
然后枚举 P 的 cnt[(]-cnt[)] 的值。
需要满足 dertap+dertaq+dertas=0
直接乘法原理即可。
比如枚举出 p[lp][dertap]，那么 lq=n-ls-lp, dertaq=-dertas-dertap
*/
#include <bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(i=l;i<=r;++i)
using namespace std;
const int N=100005,p=1e9+7;
int f[2015][2015];
char str[N];
int i,j,x,mrex=p,n,m,ret;
inline void pre()
{
	f[0][0]=1;
	rep(i,1,2005)
	{
		f[i][0]=f[i-1][1];
		rep(j,1,i)f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%p;//,printf("%d %d %d\n",i,j,f[i][j]);
	}
	return ;
}
inline int gmax()
{
	rep(i,1,m)
	{
		if(str[i]=='(')++x;else --x;
		mrex=min(mrex,x);
	}
	return mrex;
}
inline int solve()
{
	pre();
	gmax();
//	if(n>2000)printf("%d %d\n",x,mrex);
	rep(i,0,n-m)
		rep(j,0,i)
		{
			if(j>=-mrex && j+x<=n-m-i)
			{
//				printf("%d %d %d %d %d %d\n",i,j,f[i][j],n-m-i,j+x,f[n-m-i][j+x]);
				(ret+=(1ll*f[i][j]*f[n-m-i][j+x])%p)%=p;
			}
//			printf("%d %d %d\n", i, j, ret);
		}
	printf("%lld",ret);
	return 0;
}
signed main()
{
	scanf("%d %d %s", &n, &m, str+1);
	solve();
	return 0;
}